#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    //@ysh's method, only pass 13/32
    // int wiggleMaxLength(vector<int> &nums)
    // {
    //     int count = 0;
    //     int count_index = 0;
    //     int flag = 0;
    //     if (nums.size() > 1)
    //     {
    //         if (nums[1] > nums[0])
    //         {
    //             flag = 0;
    //         }
    //         else if (nums[1] < nums[0])
    //         {
    //             flag = 1;
    //         }
    //         else
    //         {
    //             for (size_t i = 2; i < nums.size(); i++)
    //             {
    //                 if (nums[i] > nums[0])
    //                 {
    //                     flag = 0;
    //                     break;
    //                 }
    //                 if (nums[i] < nums[0])
    //                 {
    //                     flag = 1;
    //                     break;
    //                 }
    //             }
    //         }
    //     }
    //     for (size_t i = 0; i < nums.size(); i++)
    //     {
    //         if (nums[i] > nums[count_index] && flag == 0)
    //         {
    //             count_index++;
    //             count++;
    //             while (nums[count_index] == nums[count_index - 1])
    //             {    int wiggleMaxLength(vector<int>& nums) {

    // }
    //                 count_index++;
    //             }
    //             flag = 1;
    //         }
    //         else if (nums[i] < nums[count_index] && flag == 1)
    //         {
    //             count_index++;
    //             count++;
    //             while (nums[count_index] == nums[count_index - 1])
    //             {
    //                 count_index++;
    //             }
    //             flag = 0;
    //         }
    //     }
    //     return count + 1;
    // }

    //@greedy_algorithm method
    //  int wiggleMaxLength(vector<int> &nums)
    //  {
    //      if (nums.size() <= 1)
    //      {
    //          return nums.size();
    //      }
    //      int result = 1;
    //      int pre_diff = 0;
    //      int cur_diff = 0;
    //      for (size_t i = 0; i < nums.size() - 1; i++)
    //      {
    //          cur_diff = nums[i + 1] - nums[i];
    //          if ((pre_diff <= 0 && cur_diff > 0) || (pre_diff >= 0 && cur_diff < 0))
    //          {
    //              result++;
    //              pre_diff = cur_diff;
    //          }
    //      }
    //      return result;
    //  }

    //@dynamic_planning
    int wiggleMaxLength(vector<int> &nums)
    {
        int dp[1005][2];
        dp[0][0] = 1;
        dp[0][1] = 1;
        for (size_t i = 1; i < nums.size(); i++)
        {
            dp[i][0] = 1;
            dp[i][1] = 1;
            for (size_t j = 0; j < i; j++)
            {
                if (nums[i] > nums[j])
                {
                    dp[i][0] = max(dp[i][0], dp[j][1] + 1);
                }
            }
            for (size_t j = 0; j < i; j++)
            {
                if (nums[i] < nums[j])
                {
                    dp[i][1] = max(dp[i][1], dp[j][0] + 1);
                }
            }
        }
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
};

int main()
{
    vector<int> nums{1, 17, 5, 10, 13, 15, 10, 5, 16, 8};
    Solution sol;
    cout << sol.wiggleMaxLength(nums) << endl;
    return 0;
}